package pers.qianyu.month_202101.date_20210114;

import java.util.*;

/**
 * 525. 连续数组
 * https://leetcode-cn.com/problems/contiguous-array/
 *
 * @author mizzle rain
 * @date 2021-01-14 15:54
 */
public class FindMaxLength {
    public int findMaxLength(int[] nums) {
        int len = nums.length;
        if (len == 0) return 0;
        for (int i = 0; i < len; i++) if (nums[i] == 0) nums[i] = -1;
        int[] pre = new int[len + 1];
        for (int i = 1; i < len + 1; i++) pre[i] = pre[i - 1] + nums[i - 1];
        HashMap<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int i = 0; i < len + 1; i++) {
            Integer index = map.get(pre[i]);
            if (index != null) res = Math.max(res, i - index);
            if (!map.containsKey(pre[i])) map.put(pre[i], i);
        }
        // pre[i] - pre[j] == 0 ==> pre[i] == pre[j]
        return res;
    }
}
